package sort.memory;

/**
 * 归并算法
 * 采用分而治之，先分后治
 * @author：涂有
 * @date 2017年11月27日 下午12:14:50
 */
public class MergeSort {
	
	public static void sort(int[] a){
		sort(a, 0, a.length - 1);
	}

	public static void sort(int[] a, int start, int end){
		if(end == start) return;
		
		//先分
		int middle = (start + end) >> 1;
		sort(a, start, middle);
		sort(a, middle + 1, end);
		
		//后治
		merge(a, start, middle, end);
	}
	
	/**
	 * 合并两个已经排好序的
	 * @author：涂有
	 * @date 2017年11月27日 下午12:31:55
	 * @param a
	 * @param start
	 * @param middle
	 * @param end
	 */
	private static void merge(int[] a, int start, int middle, int end){
		int min = start - 1;
		for(int i = middle + 1; i <= end; i++){
			int value = a[i];
			min = findInsertIndex(a, value, min + 1, i); //采用二分查找加快速度
			for(int j = i - 1; j >= min; j--){
				a[j+1] = a[j];
			}
			a[min] = value;
		}
	}
	
	private static int findInsertIndex(int[] a, int value, int start, int end){
		if(end == start || start + 1 == end){
			if(value > a[start]) return start + 1;
			else return start;
		}
		
		int middle = (start + end) >> 1;
		if(value < a[middle]) return findInsertIndex(a, value, start, middle);
		return findInsertIndex(a, value, middle + 1, end);
	}
}
